class Solution:
	# @return a list of lists of string
	def __init__(self):
		self.board = []
		self.n = None
		self.ans = []

	def solveNQueens(self, n):
		self.n = n
		self.board = [None for i in xrange(n)]
		self.dfs(0)
		return self.ans

	def dfs(self, currCol):
		if currCol >= self.n:
			self.add_ans()
			return
		for i in xrange(self.n):
			bad = False
			for j in xrange(currCol):
				if (self.board[j] == i) or (abs(self.board[j]-i) == abs(j-currCol)):
					bad = True
					break
			if not bad:
				self.board[currCol] = i
				self.dfs(currCol+1)

	def add_ans(self):
		theans = []
		for i in xrange(self.n):
			li = "."*self.board[i] + 'Q' + '.'*(self.n-self.board[i]-1)
			theans.append(li)
		self.ans.append(theans)

if __name__ == '__main__':
	so = Solution()
	ans = so.solveNQueens(5)
	for m in ans:
		print ''
		for l in m:
			print l

